public class test_49 {
    /*4. 寻找两个正序数组的中位数
困难
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5*/
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3};
        int[] nums2 = {2, 3, 4};
        System.out.println(findMedianSortedArrays(nums1, nums2));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        /*int[] bigNums = new int[nums1.length + nums2.length];
        int i = 0, j = 0, b = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] <= nums2[j]) {
                bigNums[b++] = nums1[i++];
            }else {
                bigNums[b++] = nums2[j++];
            }
        }
        while (i < nums1.length){
            bigNums[b++] = nums1[i++];
        }
        while (j < nums2.length){
            bigNums[b++] = nums2[j++];
        }
        if(bigNums.length%2==1){
            return bigNums[bigNums.length/2]+0.0;
        }
        else {
            return bigNums[bigNums.length/2-1]/2.0+bigNums[bigNums.length/2]/2.0;
        }*/
        //
        int length1 = nums1.length, length2 = nums2.length;
        if ((length1 + length2) % 2 == 1) {
            //找到中间数即可
            int mid = (length1 + length2) / 2;
            return findKNum(nums1, nums2, mid + 1) * 1.0;
        } else {
            //需要取中间的两个数的平均值
            int mid = (length1 + length2) / 2;
            return (findKNum(nums1, nums2, mid) + findKNum(nums1, nums2, mid + 1)) / 2.0;
        }
    }

    public static int findKNum(int[] nums1, int[] nums2, int k) {

        int index1 = 0, index2 = 0, length1 = nums1.length, length2 = nums2.length;
        while (true) {
            if (index1 == length1)//此时nums1已经没有任何元素，直接返回nums2中剩余元素的第k个就行
                return nums2[index2 + k - 1];
            if (index2 == length2)
                return nums1[index1 + k - 1];
            if (k == 1)//此时说明已经找完了，返回更小的那个数即可
                return Math.min(nums1[index1], nums2[index2]);
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;//控制元素不会越界
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            if (nums1[newIndex1] <= nums2[newIndex2]) {
                k = k - (newIndex1 - index1 + 1);//更新k的值（去除此次被删除的元素个数）
                index1 = newIndex1 + 1;//更新新的数组起始元素（相当于删除了）
            } else {
                k = k - (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }

    }


}
